{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #无限棋局"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #enumeration #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #枚举 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: gobang"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #无限棋局"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "小力正在通过残局练习来备战「力扣挑战赛」中的「五子棋」项目，他想请你能帮他预测当前残局的输赢情况。棋盘中的棋子分布信息记录于二维数组 `pieces` 中，其中 `pieces[i] = [x,y,color]` 表示第 `i` 枚棋子的横坐标为 `x`，纵坐标为 `y`，棋子颜色为 `color`(`0` 表示黑棋，`1` 表示白棋)。假如黑棋先行，并且黑棋和白棋都按最优策略落子，请你求出当前棋局在三步（按 **黑、白、黑** 的落子顺序）之内的输赢情况（三步之内先构成同行、列或对角线连续同颜色的至少 5 颗即为获胜）：\n",
    "- 黑棋胜, 请返回 `\"Black\"`\n",
    "- 白棋胜, 请返回 `\"White\"`\n",
    "- 仍无胜者, 请返回 `\"None\"`\n",
    "\n",
    "**注意：** \n",
    "- 和传统的五子棋项目不同，「力扣挑战赛」中的「五子棋」项目 **不存在边界限制**，即可在 **任意位置** 落子；\n",
    "- 黑棋和白棋均按 3 步内的输赢情况进行最优策略的选择\n",
    "- 测试数据保证所给棋局目前无胜者；\n",
    "- 测试数据保证不会存在坐标一样的棋子。\n",
    "\n",
    "**示例 1：**\n",
    "> 输入：\n",
    "> `pieces = [[0,0,1],[1,1,1],[2,2,0]]`\n",
    ">\n",
    "> 输出：`\"None\"`\n",
    ">\n",
    "> 解释：无论黑、白棋以何种方式落子，三步以内都不会产生胜者。\n",
    "\n",
    "**示例 2：**\n",
    "> 输入：\n",
    "> `pieces = [[1,2,1],[1,4,1],[1,5,1],[2,1,0],[2,3,0],[2,4,0],[3,2,1],[3,4,0],[4,2,1],[5,2,1]]`\n",
    ">\n",
    "> 输出：`\"Black\"`\n",
    ">\n",
    "> 解释：三步之内黑棋必胜，以下是一种可能的落子情况：\n",
    ">![902b87df29998b1c181146c8fdb3a4b6.gif](https://pic.leetcode-cn.com/1629800639-KabOfY-902b87df29998b1c181146c8fdb3a4b6.gif){:width=\"300px\"}\n",
    "\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `0 <= pieces.length <= 1000`\n",
    "- `pieces[i].length = 3`\n",
    "- `-10^9 <= pieces[i][0], pieces[i][1] <=10^9` \n",
    "- `0 <= pieces[i][2] <=1`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [fsa7oZ](https://leetcode.cn/problems/fsa7oZ/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [fsa7oZ](https://leetcode.cn/problems/fsa7oZ/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,1],[1,1,1],[2,2,0]]', '[[1,2,1],[1,4,1],[1,5,1],[2,1,0],[2,3,0],[2,4,0],[3,2,1],[3,4,0],[4,2,1],[5,2,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gobang(self, pieces: List[List[int]]) -> str:\n",
    "        dirs = [(0, 1), (1, 0), (1, 1), (1, -1)]\n",
    "        steps = [1, -1, 2, -2]\n",
    "        def myAdd(i, j, l1, l2):\n",
    "            ans = set()\n",
    "            for ii, jj in dirs:\n",
    "                for k in range(5):\n",
    "                    count = 0\n",
    "                    for l in range(5):\n",
    "                        if (i + ii * (k - l), j + jj * (k - l)) in l1:\n",
    "                            count += 1\n",
    "                        if (i + ii * (k - l), j + jj * (k - l)) in l2:\n",
    "                            count = -4\n",
    "                    if count == 4:\n",
    "                        for l in range(5):\n",
    "                            if (i + ii * (k - l), j + jj * (k - l)) not in l1 and (i + ii * (k - l), j + jj * (k - l)) not in l2:\n",
    "                                ans.add((i + ii * (k - l), j + jj * (k - l)))\n",
    "            return ans\n",
    "        def myFind(l1, l2):\n",
    "            ans = set()\n",
    "            for i, j in l1:\n",
    "                ans = ans.union(myAdd(i, j, l1, l2))\n",
    "            return ans\n",
    "        lb, lw = set(), set()\n",
    "        for i, j, k in pieces:\n",
    "            if k == 0:\n",
    "                lb.add((i, j))\n",
    "            if k == 1:\n",
    "                lw.add((i, j))\n",
    "        if len(myFind(lb, lw)) > 0:\n",
    "            return \"Black\"\n",
    "        tmp = myFind(lw, lb)\n",
    "        if len(tmp) > 1:\n",
    "            return \"White\"\n",
    "        if len(tmp) == 1:\n",
    "            lb = lb.union(tmp)\n",
    "            if len(myFind(lb, lw)) > 1:\n",
    "                return \"Black\"\n",
    "            else:\n",
    "                return \"None\"\n",
    "        lbb = lb.copy()\n",
    "        for i, j in lbb:\n",
    "            for ii, jj in dirs:\n",
    "                for step in steps:\n",
    "                    if (i + ii * step, j + jj * step) not in lb and (i + ii * step, j + jj * step) not in lw:\n",
    "                        lb.add((i + ii * step, j + jj * step))\n",
    "                        if len(myAdd(i + ii * step, j + jj * step, lb, lw)) > 1:\n",
    "                            return \"Black\"\n",
    "                        lb.remove((i + ii * step, j + jj * step))\n",
    "        return \"None\"\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef gobang(self, pieces):\n",
    "\t\tpoolB = {(x, y) for x, y, t in pieces if t == 0}\n",
    "\t\tpoolW = {(x, y) for x, y, t in pieces if t == 1}\n",
    "\t\tw1 = set()\n",
    "\t\tb2m = {}\n",
    "\t\tfor x, y in poolB:\n",
    "\t\t\tfor dx, dy in [[1,1], [1,0], [1,-1], [0,1]]:\n",
    "\t\t\t\tfor m in range(-2, 3):\n",
    "\t\t\t\t\tcnt, dots = self.chk(poolB, poolW, x + (m - 2) * dx, y + (m - 2) * dy, dx, dy)\n",
    "\t\t\t\t\tif cnt == 4:\n",
    "\t\t\t\t\t\treturn 'Black'\n",
    "\t\t\t\t\tif cnt == 3:\n",
    "\t\t\t\t\t\tfor i in range(2):\n",
    "\t\t\t\t\t\t\tif dots[i] in b2m:\n",
    "\t\t\t\t\t\t\t\tb2m[dots[i]].add(dots[i ^ 1]) #获胜须要的另一步\n",
    "\t\t\t\t\t\t\telse:\n",
    "\t\t\t\t\t\t\t\tb2m[dots[i]] = {dots[i ^ 1]}\n",
    "\t\tfor x, y in poolW:\n",
    "\t\t\tfor dx, dy in [[1,1], [1,0], [1,-1], [0,1]]:\n",
    "\t\t\t\tfor m in range(-2, 3):\n",
    "\t\t\t\t\tcnt, dots = self.chk(poolW, poolB, x + (m - 2) * dx, y + (m - 2) * dy, dx, dy)\n",
    "\t\t\t\t\tif cnt == 4:\n",
    "\t\t\t\t\t\tw1.add(dots[0])\n",
    "\t\tif len(w1) >= 2:\n",
    "\t\t\treturn 'White'\n",
    "\t\tb2 = {key for key in b2m if len(b2m[key]) >= 2}\n",
    "\t\tif b2 and (len(w1) == 0 or w1.pop() in b2):\n",
    "\t\t\treturn 'Black'\n",
    "\t\treturn 'None'\n",
    "\t\n",
    "\tdef chk(self, same, other, x, y, dx, dy):\n",
    "\t\tcnt = 0\n",
    "\t\tres = []\n",
    "\t\tfor _ in range(5):\n",
    "\t\t\tif (x, y) in other:\n",
    "\t\t\t\treturn 0, []\n",
    "\t\t\tif (x, y) in same:\n",
    "\t\t\t\tcnt += 1\n",
    "\t\t\telse:\n",
    "\t\t\t\tres.append((x, y))\n",
    "\t\t\tx += dx\n",
    "\t\t\ty += dy\n",
    "\t\treturn cnt, res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\r\n",
    "class Solution:\r\n",
    "    def gobang(self, pieces: List[List[int]]) -> str:\r\n",
    "        B = [defaultdict(SortedList) for _ in range(4)] # 黑棋的四类直线：水平, 垂直, 斜率为1, 斜率为-1\r\n",
    "        W = [defaultdict(SortedList) for _ in range(4)] # 白棋的四类直线：水平, 垂直, 斜率为1, 斜率为-1\r\n",
    "\r\n",
    "        def add_piece(x, y, c):\r\n",
    "            P = W if c else B\r\n",
    "            P[0][y].add(x)\r\n",
    "            P[1][x].add(y)\r\n",
    "            P[2][y - x].add(x)\r\n",
    "            P[3][y + x].add(x)\r\n",
    "\r\n",
    "        def get_pos(k, v, d):\r\n",
    "            if d == 0: x, y = v, k\r\n",
    "            elif d == 1: x, y = k, v\r\n",
    "            elif d == 2: x, y = v, k + v\r\n",
    "            elif d == 3: x, y = v, k - v\r\n",
    "            return (x, y)\r\n",
    "\r\n",
    "        # 找到P的棋子中，冲np(3或4)的点（填上这个点就必胜，并且没有Q的棋子阻挡）\r\n",
    "        def find_win_ps(P, Q, np) -> defaultdict(set):\r\n",
    "            win_points = defaultdict(set)\r\n",
    "            for d in range(4):\r\n",
    "                for k in P[d]:\r\n",
    "                    ps, n = P[d][k], len(P[d][k])\r\n",
    "                    if n < np: continue\r\n",
    "                    for i in range(n + 1 - np):\r\n",
    "                        dif = ps[i + np - 1] - ps[i]\r\n",
    "                        if dif < 5: # <5 说明能成5\r\n",
    "                            # 找出空缺的v。找规律发现在[ps[i]-(4-dif), ps[i] + 5]，不是已有的v的点\r\n",
    "                            vs = [v for v in range(ps[i] + dif - 4, ps[i] + 5) if\r\n",
    "                                  v not in ps[i:i + np] and not has_piece(Q, (k, v, d))]\r\n",
    "                            nvs = len(vs)\r\n",
    "                            if nvs < 5 - np: continue  # 3->2, 4->1\r\n",
    "                            dt = 4 - np\r\n",
    "                            for j in range(nvs - dt):\r\n",
    "                                v1, v2 = vs[j], vs[j + dt]\r\n",
    "                                if v2 - v1 > 4: continue\r\n",
    "                                xy1, xy2 = get_pos(k, v1, d), get_pos(k, v2, d)\r\n",
    "                                win_points[xy1].add(xy2)\r\n",
    "                                win_points[xy2].add(xy1)\r\n",
    "                                if np == 4 and len(win_points) > 1: return win_points\r\n",
    "            return win_points\r\n",
    "\r\n",
    "        def has_piece(X, kvd) -> bool:\r\n",
    "            k, v, d = kvd\r\n",
    "            return k in X[d] and v in X[d][k]\r\n",
    "\r\n",
    "        # 开始，棋子先存好\r\n",
    "        for x, y, c in pieces:\r\n",
    "            add_piece(x, y, c)\r\n",
    "\r\n",
    "        # 1. 黑先手有4连黑子，并且有空位放下能成5连黑子，就黑胜\r\n",
    "        if len(find_win_ps(B, W, 4)) > 0:\r\n",
    "            return 'Black'\r\n",
    "\r\n",
    "        # 白如果有多个冲4就赢\r\n",
    "        live_w4 = find_win_ps(W, B, 4)\r\n",
    "        if len(live_w4) > 1:\r\n",
    "            return 'White'\r\n",
    "\r\n",
    "        # 白只有1个冲4，黑先堵上；如果黑有多个冲4就赢，否则None\r\n",
    "        if len(live_w4) == 1:\r\n",
    "            x, y = list(live_w4.keys())[0]\r\n",
    "            add_piece(x, y, 0)\r\n",
    "            return 'Black' if len(find_win_ps(B, W, 4)) > 1 else 'None'\r\n",
    "\r\n",
    "        # 检查最开始如果有形成双4的点，就黑赢\r\n",
    "        return 'Black' if any(len(ds) > 1 for ds in find_win_ps(B, W, 3).values()) else 'None'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def gobang(self, pieces: List[List[int]]) -> str:\n",
    "        B = [defaultdict(SortedList) for _ in range(4)] \n",
    "        W = [defaultdict(SortedList) for _ in range(4)] \n",
    "\n",
    "        def add_piece(x, y, c):\n",
    "            P = W if c else B\n",
    "            P[0][y].add(x)\n",
    "            P[1][x].add(y)\n",
    "            P[2][y - x].add(x)\n",
    "            P[3][y + x].add(x)\n",
    "\n",
    "        def get_pos(k, v, d):\n",
    "            if d == 0: x, y = v, k\n",
    "            elif d == 1: x, y = k, v\n",
    "            elif d == 2: x, y = v, k + v\n",
    "            elif d == 3: x, y = v, k - v\n",
    "            return (x, y)\n",
    "        \n",
    "        def find_win_ps(P, Q, np) -> defaultdict(set):\n",
    "            win_points = defaultdict(set)\n",
    "            for d in range(4):\n",
    "                for k in P[d]:\n",
    "                    ps, n = P[d][k], len(P[d][k])\n",
    "                    if n < np: continue\n",
    "                    for i in range(n + 1 - np):\n",
    "                        dif = ps[i + np - 1] - ps[i]\n",
    "                        if dif < 5: # <5 \n",
    "                            vs = [v for v in range(ps[i] + dif - 4, ps[i] + 5) if\n",
    "                                  v not in ps[i:i + np] and not has_piece(Q, (k, v, d))]\n",
    "                            nvs = len(vs)\n",
    "                            if nvs < 5 - np: continue  \n",
    "                            dt = 4 - np\n",
    "                            for j in range(nvs - dt):\n",
    "                                v1, v2 = vs[j], vs[j + dt]\n",
    "                                if v2 - v1 > 4: continue\n",
    "                                xy1, xy2 = get_pos(k, v1, d), get_pos(k, v2, d)\n",
    "                                win_points[xy1].add(xy2)\n",
    "                                win_points[xy2].add(xy1)\n",
    "                                if np == 4 and len(win_points) > 1: return win_points\n",
    "            return win_points\n",
    "        def has_piece(X, kvd) -> bool:\n",
    "            k, v, d = kvd\n",
    "            return k in X[d] and v in X[d][k]\n",
    "\n",
    "        # 开始，棋子先存好\n",
    "        for x, y, c in pieces:\n",
    "            add_piece(x, y, c)\n",
    "\n",
    "        # 1. 黑先手有4连黑子，并且有空位放下能成5连黑子，就黑胜\n",
    "        if len(find_win_ps(B, W, 4)) > 0:\n",
    "            return 'Black'\n",
    "\n",
    "        # 白如果有多个冲4就赢\n",
    "        live_w4 = find_win_ps(W, B, 4)\n",
    "        if len(live_w4) > 1:\n",
    "            return 'White'\n",
    "\n",
    "        # 白只有1个冲4，黑先堵上；如果黑有多个冲4就赢，否则None\n",
    "        if len(live_w4) == 1:\n",
    "            x, y = list(live_w4.keys())[0]\n",
    "            add_piece(x, y, 0)\n",
    "            return 'Black' if len(find_win_ps(B, W, 4)) > 1 else 'None'\n",
    "\n",
    "        # 检查最开始如果有形成双4的点，就黑赢\n",
    "        return 'Black' if any(len(ds) > 1 for ds in find_win_ps(B, W, 3).values()) else 'None'\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gobang(self, pieces: List[List[int]]) -> str:\n",
    "        D = [(1, 0), (0, 1), (1, 1), (-1, 1)]\n",
    "        board = {(x,y):c for x, y, c in pieces}\n",
    "\n",
    "        # 枚举指定颜色棋子五子连线的所有方案（当前棋盘额外最多下两子）\n",
    "        def findLines(color) :\n",
    "            lines = DefaultDict(list)\n",
    "            for x, y, c in pieces : # 枚举棋盘上所有指定颜色棋子的位置\n",
    "                if c != color : continue\n",
    "                for i, (dx, dy) in enumerate(D) : # 连线有四个方向\n",
    "                    for k in range(3) : # 因为最多额外下两子，连线端点偏离已有棋子不超过2\n",
    "                        nx, ny = x-dx*k, y-dy*k\n",
    "                        head = (nx, ny, i)\n",
    "                        if head in lines : continue # 该“端点&方向”已存在\n",
    "\n",
    "                        for _ in range(5) : # 把该连线上剩下的落子位找到\n",
    "                            c = board.get((nx, ny), -1)\n",
    "                            if c != color :\n",
    "                                if c >= 0 or len(lines[head]) >= 2 : # 该连线上有异色棋子，或空位过多，舍弃\n",
    "                                    lines[head].clear()\n",
    "                                    break\n",
    "                                lines[head].append((nx, ny))\n",
    "                            nx, ny = nx+dx, ny+dy\n",
    "\n",
    "            # 按待落子数归类连线方案\n",
    "            res = [[] for _ in range(3)]\n",
    "            for v in lines.values() :\n",
    "                if len(v) : res[len(v)].append(v)\n",
    "            return res\n",
    "\n",
    "        # 若黑棋存在一步致胜的方案，则黑胜\n",
    "        black = findLines(0)\n",
    "        if len(black[1]) > 0 : return \"Black\"\n",
    "\n",
    "        white = findLines(1)\n",
    "        positions = set(line[0] for line in white[1]) # 不同的连线可能包含相同的落子位，须去重\n",
    "        # 若白棋存在多个一步制胜的落子位，则白胜\n",
    "        if len(positions) > 1 : return \"White\"\n",
    "\n",
    "        if len(positions) == 1 :\n",
    "            # 若白棋存在一个一步制胜的落子位，则黑先手必须堵这个位置\n",
    "            x, y = positions.pop()\n",
    "            pieces.append([x, y, 0])\n",
    "            board[(x, y)] = 0\n",
    "            black = findLines(0)\n",
    "\n",
    "            # 黑棋堵位后，黑棋存在多个一步制胜的落子位，则黑剩，否则平\n",
    "            positions = set(line[0] for line in black[1])\n",
    "            return \"Black\" if len(positions) > 1 else \"None\"\n",
    "\n",
    "        # 若白棋不存在一步制胜的落子位，黑须落一子创造多于一个一步制胜的落子位才能在两步内获胜\n",
    "        pairs = set((pair[0], pair[1]) for pair in black[2]) # 不同的连线可能包含相同的两个落子位，须去重\n",
    "        positions = set()\n",
    "        for p1, p2 in pairs :\n",
    "            # 若某个落子位在之前落子对中已出现，下该位置能产生两个一步致胜的位置\n",
    "            if p1 in positions or p2 in positions : return \"Black\"\n",
    "            positions.add(p1)\n",
    "            positions.add(p2)\n",
    "\n",
    "        return \"None\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gobang(self, pieces: List[List[int]]) -> str:\n",
    "        D = [(1, 0), (0, 1), (1, 1), (-1, 1)]\n",
    "        board = {(x,y):c for x, y, c in pieces}\n",
    "\n",
    "        # 枚举指定颜色棋子五子连线的所有方案（当前棋盘额外最多下两子）\n",
    "        def findLines(color) :\n",
    "            lines = DefaultDict(list)\n",
    "            for x, y, c in pieces : # 枚举棋盘上所有指定颜色棋子的位置\n",
    "                if c != color : continue\n",
    "                for i, (dx, dy) in enumerate(D) : # 连线有四个方向\n",
    "                    for k in range(3) : # 因为最多额外下两子，连线端点偏离已有棋子不超过2\n",
    "                        nx, ny = x-dx*k, y-dy*k\n",
    "                        head = (nx, ny, i)\n",
    "                        if head in lines : continue # 该“端点&方向”已存在\n",
    "\n",
    "                        for _ in range(5) : # 把该连线上剩下的落子位找到\n",
    "                            c = board.get((nx, ny), -1)\n",
    "                            if c != color :\n",
    "                                if c >= 0 or len(lines[head]) >= 2 : # 该连线上有异色棋子，或空位过多，舍弃\n",
    "                                    lines[head].clear()\n",
    "                                    break\n",
    "                                lines[head].append((nx, ny))\n",
    "                            nx, ny = nx+dx, ny+dy\n",
    "\n",
    "            # 按待落子数归类连线方案\n",
    "            res = [[] for _ in range(3)]\n",
    "            for v in lines.values() :\n",
    "                if len(v) : res[len(v)].append(v)\n",
    "            return res\n",
    "\n",
    "        # 若黑棋存在一步致胜的方案，则黑胜\n",
    "        black = findLines(0)\n",
    "        if len(black[1]) > 0 : return \"Black\"\n",
    "\n",
    "        white = findLines(1)\n",
    "        positions = set(line[0] for line in white[1]) # 不同的连线可能包含相同的落子位，须去重\n",
    "        # 若白棋存在多个一步制胜的落子位，则白胜\n",
    "        if len(positions) > 1 : return \"White\"\n",
    "\n",
    "        if len(positions) == 1 :\n",
    "            # 若白棋存在一个一步制胜的落子位，则黑先手必须堵这个位置\n",
    "            x, y = positions.pop()\n",
    "            pieces.append([x, y, 0])\n",
    "            board[(x, y)] = 0\n",
    "            black = findLines(0)\n",
    "\n",
    "            # 黑棋堵位后，黑棋存在多个一步制胜的落子位，则黑剩，否则平\n",
    "            positions = set(line[0] for line in black[1])\n",
    "            return \"Black\" if len(positions) > 1 else \"None\"\n",
    "\n",
    "        # 若白棋不存在一步制胜的落子位，黑须落一子创造多于一个一步制胜的落子位才能在两步内获胜\n",
    "        pairs = set((pair[0], pair[1]) for pair in black[2]) # 不同的连线可能包含相同的两个落子位，须去重\n",
    "        positions = set()\n",
    "        for p1, p2 in pairs :\n",
    "            # 若某个落子位在之前落子对中已出现，下该位置能产生两个一步致胜的位置\n",
    "            if p1 in positions or p2 in positions : return \"Black\"\n",
    "            positions.add(p1)\n",
    "            positions.add(p2)\n",
    "\n",
    "        return \"None\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 当前问题，具体解法如下：\n",
    "# 获取黑1步胜的点集。\n",
    "# 如果该点集不位空，则黑胜结束。\n",
    "# 获取白1步胜的点集。\n",
    "# 如果该点集数目大于等于2，则白色胜结束。\n",
    "# 如果该点集数目等于1，则黑走此处。问题转化为\"从该棋子出发1步胜的点集数目是否大于等于2\"，解这个问题，结束。\n",
    "# 黑2步胜？如果胜，则黑胜结束。\n",
    "# 平局结束。\n",
    "\n",
    "# 子问题：获取某色1步胜的点集，具体解法如下：\n",
    "# 结果点集 = 空集\n",
    "# 对当前颜色的每个棋子：\n",
    "#   获取从该棋子出发1步胜的点集，并入到结果点集中。\n",
    "#   如果点集数目大于等于2，则直接返回结果点集。（没必要继续计算了）\n",
    "# 返回结果点集。\n",
    "\n",
    "# 子问题：获取从某个棋子出发1步胜的点集，具体解法如下：\n",
    "# 结果点集 = 空集\n",
    "# 如果当前棋子作为一横5连位置的第1，2，3，4，5个位置的时候，分5次判断：如果出现4个当前色和一个空位，则把这个空位加入到结果点集中。\n",
    "# 如果当前棋子作为一竖5连位置的第1，2，3，4，5个位置的时候，分5次判断：如果出现4个当前色和一个空位，则把这个空位加入到结果点集中。\n",
    "# 如果当前棋子作为一撇5连位置的第1，2，3，4，5个位置的时候，分5次判断：如果出现4个当前色和一个空位，则把这个空位加入到结果点集中。\n",
    "# 如果当前棋子作为一捺5连位置的第1，2，3，4，5个位置的时候，分5次判断：如果出现4个当前色和一个空位，则把这个空位加入到结果点集中。\n",
    "# 注意，在上述共20次判断中，如果任何一次，发现结果点集合数目大于等于2，则可以直接返回结果点集。（没必要继续计算了）\n",
    "# 返回结果点集。\n",
    "\n",
    "# 子问题：某色2步胜？具体解法如下：\n",
    "# 找出当前色的直线2步缓冲区点的集合。\n",
    "# 所谓\"直线2步缓冲区点\"，指的是某个空地，从它往8个方向的任一方向，走1步可以到达当前色棋子，或直线走2步(经过一个空地)可以到达当前色棋子。\n",
    "# 因为，要想2步胜，第一步必须下在这个集合中。\n",
    "# 对于该集合中的每个点：\n",
    "#  着一步棋在这里。\n",
    "#  获取从刚下棋子出发1步胜的点集，如果点集数目大于等于2，则返回True。\n",
    "#  回一步棋。\n",
    "# 返回False。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.mat = defaultdict(int)  # 棋盘，0表示空地，1表示黑棋，2表示白棋。\n",
    "        self.dir_deltas = ((0, 1), (1, 0), (-1, 1), (1, 1))  # 横竖撇捺的递增值\n",
    "\n",
    "    # 子问题：获取从某个棋子出发1步胜的点集。\n",
    "    def oneStepWinFromPoint(self, i0, j0, cur_color):\n",
    "        assert cur_color != 0 and cur_color == self.mat[(i0, j0)]\n",
    "        ans = set()\n",
    "        for di, dj in self.dir_deltas:\n",
    "            for step in range(5):\n",
    "                oi, oj = i0 - di * step, j0 - dj * step  # 起点\n",
    "                same_color_cnt = 0\n",
    "                space_cnt = 0\n",
    "                space_i = 0\n",
    "                space_j = 0\n",
    "                for k in range(5):\n",
    "                    i = oi + di * k\n",
    "                    j = oj + dj * k\n",
    "                    color = self.mat[(i, j)]\n",
    "                    if color == 0:\n",
    "                        space_cnt += 1\n",
    "                        if space_cnt == 1:\n",
    "                            space_i = i\n",
    "                            space_j = j\n",
    "                        else:\n",
    "                            break\n",
    "                    elif color == cur_color:\n",
    "                        same_color_cnt += 1\n",
    "                    else:\n",
    "                        break\n",
    "                if same_color_cnt == 4 and space_cnt == 1:\n",
    "                    ans.add((space_i, space_j))\n",
    "                    if len(ans) >= 2:\n",
    "                        return ans\n",
    "        return ans\n",
    "\n",
    "    # 子问题：获取某色1步胜的点集\n",
    "    def oneStepWin(self, cur_color):\n",
    "        assert cur_color != 0\n",
    "        ans = set()\n",
    "        tmp = self.mat.copy()  # 这是因为使用了defaultdict，它是查询也会变更的。\n",
    "        for (i, j), color in tmp.items():\n",
    "            if color != cur_color:\n",
    "                continue\n",
    "            s = self.oneStepWinFromPoint(i, j, color)\n",
    "            ans.update(s)\n",
    "            if len(ans) >= 2:\n",
    "                return ans\n",
    "        return ans\n",
    "\n",
    "    # 获取一个点周围的直线2步缓冲区点的集合\n",
    "    def getBufferFromPoint(self, i0, j0, cur_color):\n",
    "        assert cur_color != 0 and self.mat[(i0, j0)] == cur_color\n",
    "        ans = set()\n",
    "        for (di, dj) in self.dir_deltas:\n",
    "            for factor in (-1, 1):\n",
    "                di *= factor\n",
    "                dj *= factor\n",
    "                i = i0 + di\n",
    "                j = j0 + dj\n",
    "                if self.mat[(i, j)] != 0:\n",
    "                    continue\n",
    "                ans.add((i, j))\n",
    "                i += di\n",
    "                j += dj\n",
    "                if self.mat[(i, j)] != 0:\n",
    "                    continue\n",
    "                ans.add((i, j))\n",
    "        return ans\n",
    "\n",
    "    # 获取直线2步缓冲区点的集合\n",
    "    def getBuffer(self, cur_color):\n",
    "        ans = set()\n",
    "        for (i, j), color in self.mat.items():\n",
    "            if color != cur_color:\n",
    "                continue\n",
    "            points = self.getBufferFromPoint(i, j, cur_color)\n",
    "            ans.update(points)\n",
    "        return ans\n",
    "\n",
    "    # 子问题：某色2步胜？\n",
    "    def twoStepWin(self, cur_color):\n",
    "        assert cur_color != 0\n",
    "        points = self.getBuffer(cur_color)\n",
    "        for i, j in points:\n",
    "            assert self.mat[(i, j)] == 0\n",
    "            self.mat[(i, j)] = cur_color\n",
    "            win_points = self.oneStepWinFromPoint(i, j, cur_color)\n",
    "            if len(win_points) >= 2:\n",
    "                return True\n",
    "            self.mat.pop((i, j))\n",
    "        return False\n",
    "\n",
    "    def gobang(self, pieces: List[List[int]]) -> str:\n",
    "        for i, j, color in pieces:\n",
    "            self.mat[(i, j)] = color + 1\n",
    "        black_win_points = self.oneStepWin(1)\n",
    "        if len(black_win_points) >= 1:\n",
    "            return \"Black\"\n",
    "        white_win_points = self.oneStepWin(2)\n",
    "        if len(white_win_points) >= 2:\n",
    "            return \"White\"\n",
    "        if len(white_win_points) == 1:\n",
    "            i, j = white_win_points.pop()\n",
    "            self.mat[(i, j)] = 1\n",
    "            points = self.oneStepWinFromPoint(i, j, 1)\n",
    "            if len(points) >= 2:\n",
    "                return \"Black\"\n",
    "            else:\n",
    "                return \"None\"\n",
    "        if self.twoStepWin(1):\n",
    "            return \"Black\"\n",
    "        return \"None\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 当前问题，具体解法如下：\n",
    "# 获取黑1步胜的点集。\n",
    "# 如果该点集不位空，则黑胜结束。\n",
    "# 获取白1步胜的点集。\n",
    "# 如果该点集数目大于等于2，则白色胜结束。\n",
    "# 如果该点集数目等于1，则黑走此处。问题转化为\"从该棋子出发1步胜的点集数目是否大于等于2\"，解这个问题，结束。\n",
    "# 黑2步胜？如果胜，则黑胜结束。\n",
    "# 平局结束。\n",
    "\n",
    "# 子问题：获取某色1步胜的点集，具体解法如下：\n",
    "# 结果点集 = 空集\n",
    "# 对当前颜色的每个棋子：\n",
    "#   获取从该棋子出发1步胜的点集，并入到结果点集中。\n",
    "#   如果点集数目大于等于2，则直接返回结果点集。（没必要继续计算了）\n",
    "# 返回结果点集。\n",
    "\n",
    "# 子问题：获取从某个棋子出发1步胜的点集，具体解法如下：\n",
    "# 结果点集 = 空集\n",
    "# 如果当前棋子作为一横5连位置的第1，2，3，4，5个位置的时候，分5次判断：如果出现4个当前色和一个空位，则把这个空位加入到结果点集中。\n",
    "# 如果当前棋子作为一竖5连位置的第1，2，3，4，5个位置的时候，分5次判断：如果出现4个当前色和一个空位，则把这个空位加入到结果点集中。\n",
    "# 如果当前棋子作为一撇5连位置的第1，2，3，4，5个位置的时候，分5次判断：如果出现4个当前色和一个空位，则把这个空位加入到结果点集中。\n",
    "# 如果当前棋子作为一捺5连位置的第1，2，3，4，5个位置的时候，分5次判断：如果出现4个当前色和一个空位，则把这个空位加入到结果点集中。\n",
    "# 注意，在上述共20次判断中，如果任何一次，发现结果点集合数目大于等于2，则可以直接返回结果点集。（没必要继续计算了）\n",
    "# 返回结果点集。\n",
    "\n",
    "# 子问题：某色2步胜？具体解法如下：\n",
    "# 找出当前色的直线2步缓冲区点的集合。\n",
    "# 所谓\"直线2步缓冲区点\"，指的是某个空地，从它往8个方向的任一方向，走1步可以到达当前色棋子，或直线走2步(经过一个空地)可以到达当前色棋子。\n",
    "# 因为，要想2步胜，第一步必须下在这个集合中。\n",
    "# 对于该集合中的每个点：\n",
    "#  着一步棋在这里。\n",
    "#  获取从刚下棋子出发1步胜的点集，如果点集数目大于等于2，则返回True。\n",
    "#  回一步棋。\n",
    "# 返回False。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.mat = defaultdict(int)  # 棋盘，0表示空地，1表示黑棋，2表示白棋。\n",
    "        self.dir_deltas = ((0, 1), (1, 0), (-1, 1), (1, 1))  # 横竖撇捺的递增值\n",
    "\n",
    "    # 子问题：获取从某个棋子出发1步胜的点集。\n",
    "    def oneStepWinFromPoint(self, i0, j0, cur_color):\n",
    "        assert cur_color != 0 and cur_color == self.mat[(i0, j0)]\n",
    "        ans = set()\n",
    "        for di, dj in self.dir_deltas:\n",
    "            for step in range(5):\n",
    "                oi, oj = i0 - di * step, j0 - dj * step  # 起点\n",
    "                same_color_cnt = 0\n",
    "                space_cnt = 0\n",
    "                space_i = 0\n",
    "                space_j = 0\n",
    "                for k in range(5):\n",
    "                    i = oi + di * k\n",
    "                    j = oj + dj * k\n",
    "                    color = self.mat[(i, j)]\n",
    "                    if color == 0:\n",
    "                        space_cnt += 1\n",
    "                        if space_cnt == 1:\n",
    "                            space_i = i\n",
    "                            space_j = j\n",
    "                        else:\n",
    "                            break\n",
    "                    elif color == cur_color:\n",
    "                        same_color_cnt += 1\n",
    "                    else:\n",
    "                        break\n",
    "                if same_color_cnt == 4 and space_cnt == 1:\n",
    "                    ans.add((space_i, space_j))\n",
    "                    if len(ans) >= 2:\n",
    "                        return ans\n",
    "        return ans\n",
    "\n",
    "    # 子问题：获取某色1步胜的点集\n",
    "    def oneStepWin(self, cur_color):\n",
    "        assert cur_color != 0\n",
    "        ans = set()\n",
    "        tmp = self.mat.copy()  # 这是因为使用了defaultdict，它是查询也会变更的。\n",
    "        for (i, j), color in tmp.items():\n",
    "            if color != cur_color:\n",
    "                continue\n",
    "            s = self.oneStepWinFromPoint(i, j, color)\n",
    "            ans.update(s)\n",
    "            if len(ans) >= 2:\n",
    "                return ans\n",
    "        return ans\n",
    "\n",
    "    # 获取一个点周围的直线2步缓冲区点的集合\n",
    "    def getBufferFromPoint(self, i0, j0, cur_color):\n",
    "        assert cur_color != 0 and self.mat[(i0, j0)] == cur_color\n",
    "        ans = set()\n",
    "        for (di, dj) in self.dir_deltas:\n",
    "            for factor in (-1, 1):\n",
    "                di *= factor\n",
    "                dj *= factor\n",
    "                i = i0 + di\n",
    "                j = j0 + dj\n",
    "                if self.mat[(i, j)] != 0:\n",
    "                    continue\n",
    "                ans.add((i, j))\n",
    "                i += di\n",
    "                j += dj\n",
    "                if self.mat[(i, j)] != 0:\n",
    "                    continue\n",
    "                ans.add((i, j))\n",
    "        return ans\n",
    "\n",
    "    # 获取直线2步缓冲区点的集合\n",
    "    def getBuffer(self, cur_color):\n",
    "        ans = set()\n",
    "        for (i, j), color in self.mat.items():\n",
    "            if color != cur_color:\n",
    "                continue\n",
    "            points = self.getBufferFromPoint(i, j, cur_color)\n",
    "            ans.update(points)\n",
    "        return ans\n",
    "\n",
    "    # 子问题：某色2步胜？\n",
    "    def twoStepWin(self, cur_color):\n",
    "        assert cur_color != 0\n",
    "        points = self.getBuffer(cur_color)\n",
    "        for i, j in points:\n",
    "            assert self.mat[(i, j)] == 0\n",
    "            self.mat[(i, j)] = cur_color\n",
    "            win_points = self.oneStepWinFromPoint(i, j, cur_color)\n",
    "            if len(win_points) >= 2:\n",
    "                return True\n",
    "            self.mat.pop((i, j))\n",
    "        return False\n",
    "\n",
    "    def gobang(self, pieces: List[List[int]]) -> str:\n",
    "        for i, j, color in pieces:\n",
    "            self.mat[(i, j)] = color + 1\n",
    "        black_win_points = self.oneStepWin(1)\n",
    "        if len(black_win_points) >= 1:\n",
    "            return \"Black\"\n",
    "        white_win_points = self.oneStepWin(2)\n",
    "        if len(white_win_points) >= 2:\n",
    "            return \"White\"\n",
    "        if len(white_win_points) == 1:\n",
    "            i, j = white_win_points.pop()\n",
    "            self.mat[(i, j)] = 1\n",
    "            points = self.oneStepWinFromPoint(i, j, 1)\n",
    "            if len(points) >= 2:\n",
    "                return \"Black\"\n",
    "            else:\n",
    "                return \"None\"\n",
    "        if self.twoStepWin(1):\n",
    "            return \"Black\"\n",
    "        return \"None\""
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
